/*
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-partitioning
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> item;
        dfs(s,item,res);
        return res;
    }

private:
    void dfs(string str,vector<string>& item,vector<vector<string>>& res){
        if(str.size()==0){
            res.push_back(item);
            return;
        }
        string sub;
        for(int i=1;i<=str.size();i++){
            sub=str.substr(0,i);
            if(huiwen(sub)){
                item.push_back(sub);
                dfs(str.substr(i,str.size()-i),item,res);
                item.pop_back();
            }
        }
    }

    bool huiwen(string& str){
        int i=0;
        int j=str.size()-1;
        while(i<j){
            if(str[i]!=str[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
};